package demo2;

import java.util.List;

public class MyLinkedList {
    public ListNode head;

    public void creatList() {
        ListNode listNode1 = new ListNode(21);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(27);
        ListNode listNode4 = new ListNode(28);
        ListNode listNode5 = new ListNode(24);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
       // listNode5.next = listNode3;
        this.head = listNode1;
    }

    public void disPlay() {
        ListNode cur = this.head;
        if (isEmpty()) {
            System.out.println("链表为空!");
            return;
        }
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public boolean isEmpty() {
        return this.head == null ? true : false;
    }

    //判断链表是否为回文
    public boolean isPalindrome() {
        ListNode fast = this.head;
        ListNode slow = this.head;

        //取的中间值
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //逆反
        ListNode cur = slow.next;
        //ListNode curNext = cur.next;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        //判断回文
        ListNode head1 = this.head;
        while (head1 != slow && head1.next != slow) {
            if (head1.val == slow.val) {
                head1 = head1.next;
                slow = slow.next;
            } else {
                return false;
            }
        }
        //奇数
        if (head1 == slow) {
            return true;
        }
        //偶数
        if (head1.next == slow) {
            if (head1.val == slow.val) {
                return true;
            }else {
                return false;
            }
        }
        return true;
    }


    //判断两个链表是否有节点
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            System.out.println("有空节点所以  相交节点为空!");
            return null;
        }
        int lenA = getListNodelength(headA);
        int lenB = getListNodelength(headB);
        ListNode pl = null;
        ListNode ps = null;

        if (lenA > lenB) {
             pl = headA;
             ps = headB;
        } else {
             pl = headB;
             ps = headA;
        }

        //求两个链表长度差
        int dif = lenA - lenB;

        //将最长的链表移动到两个链表长度相同的位置
        while (dif-- > 0) {
            pl = pl.next;
        }

        //两个节点同时向后走
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }

        //判断是不是没有交点  并且两个链表都走到了null
       /* if (pl != null) {
            return pl;
        }
        return null;*/

       return pl;

    }

    //判断是不是链表中是不是有环
    public boolean judgementRingListNode(ListNode listNode) {
        ListNode fast = listNode;
        ListNode slow = listNode;
        while (fast.next != null && fast != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    public ListNode detectCycle() {
        ListNode fast = this.head;
        ListNode slow = this.head;
        while (fast.next != null && fast != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                break;
            }
        }
        //如果走到空  证明不是链表中不存在环
        if (fast.next == null || fast == null) {
            return null;
        }
        fast = this.head;

        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;

    }

    //判断链表长度
    public int getListNodelength(ListNode headA) {
        int count = 0;
        while (headA != null) {
            headA = headA.next;
            count++;
        }
        return count;
    }



}
